package pers.vic.basics.leetcode;

import java.util.Arrays;

/**
 * @author Vic.xu
 * @description: 31. 下一个排列 {@literal https://leetcode-cn.com/problems/next-permutation/}
 * @date: 2020/11/20 17:59
 */
public class J0031_M_NextPermutation {
    /*
    实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
    如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
    必须 原地 修改，只允许使用额外常数空间。
     */

    /**
     * 要是不看别人解题  连题目都没看懂
     * 原序列 ： 1 2 3 4 6 5---> 1 2 3 5 4 6
     * a. 后面的大数与前面的小数交换，小数尽量靠右，大树尽可能小
     * b. 交换后大数后面的数重排序-升序
     * ------
     * 意为：从后往前找到一个降序，然后这个位置后面最小的数和这个位置交换后，重排序其后的
     */
    public static void nextPermutation(int[] nums) {
        int len = nums.length;
        for (int i = len - 1; i >= 0; i--) {
            //没有找到降序的  直接重排序
            if (i == 0) {
                Arrays.sort(nums);
            } else if ((nums[i] > nums[i - 1])) {
                //找到降序的位置，  然后用后面 大于此数的数（最小的大数） 和它交换，交换完毕之后再把后面的数排序

                //先把后面的数排序 方便找到 最小的大数
                Arrays.sort(nums, i, len);
                // 此时的i以及其后的数已经升序顺序了  此时只要找到大于i-1的数即可交换
                for (int j = i; j < len ; j++) {
                    if (nums[j] > nums[i-1]) {
                        int temp = nums[i-1];
                        nums[i-1] = nums[j];
                        nums[j] = temp;
                        return;
                    }
                }
                return;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(Arrays.toString(nums));
        nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }
}
